



<!doctype html>
<html lang="zh" class="no-js">
  <head>
    
      <meta charset="utf-8">
      <meta name="viewport" content="width=device-width,initial-scale=1">
      <meta http-equiv="x-ua-compatible" content="ie=edge">
      
        <meta name="description" content="Hrbust_ACM's Wiki">
      
      
        <link rel="canonical" href="https://hrbust-acm.online/Geometry/%E5%87%B8%E5%8C%85%E7%9A%84%E6%B1%82%E5%8F%96/">
      
      
        <meta name="author" content="Hrbust_Acmer">
      
      
        <meta name="lang:clipboard.copy" content="复制">
      
        <meta name="lang:clipboard.copied" content="已复制">
      
        <meta name="lang:search.language" content="ja">
      
        <meta name="lang:search.pipeline.stopwords" content="True">
      
        <meta name="lang:search.pipeline.trimmer" content="True">
      
        <meta name="lang:search.result.none" content="没有找到符合条件的结果">
      
        <meta name="lang:search.result.one" content="找到 1 个符合条件的结果">
      
        <meta name="lang:search.result.other" content="# 个符合条件的结果">
      
        <meta name="lang:search.tokenizer" content="[\uff0c\u3002]+">
      
      <link rel="shortcut icon" href="../../assets/images/favicon.png">
      <meta name="generator" content="mkdocs-1.1, mkdocs-material-4.6.3">
    
    
      
        <title>凸包的求取 - Hrbust_ACM's Wiki</title>
      
    
    
      <link rel="stylesheet" href="../../assets/stylesheets/application.adb8469c.css">
      
        <link rel="stylesheet" href="../../assets/stylesheets/application-palette.a8b3c06d.css">
      
      
        
        
        <meta name="theme-color" content="#ef5350">
      
    
    
      <script src="../../assets/javascripts/modernizr.86422ebf.js"></script>
    
    
      
        <link href="https://fonts.gstatic.com" rel="preconnect" crossorigin>
        <link rel="stylesheet" href="https://fonts.googleapis.com/css?family=Roboto:300,400,400i,700%7CRoboto+Mono&display=fallback">
        <style>body,input{font-family:"Roboto","Helvetica Neue",Helvetica,Arial,sans-serif}code,kbd,pre{font-family:"Roboto Mono","Courier New",Courier,monospace}</style>
      
    
    <link rel="stylesheet" href="../../assets/fonts/material-icons.css">
    
    
    
      
    
    
  </head>
  
    
    
    <body dir="ltr" data-md-color-primary="red" data-md-color-accent="blue">
  
    <svg class="md-svg">
      <defs>
        
        
          <svg xmlns="http://www.w3.org/2000/svg" width="416" height="448" viewBox="0 0 416 448" id="__github"><path fill="currentColor" d="M160 304q0 10-3.125 20.5t-10.75 19T128 352t-18.125-8.5-10.75-19T96 304t3.125-20.5 10.75-19T128 256t18.125 8.5 10.75 19T160 304zm160 0q0 10-3.125 20.5t-10.75 19T288 352t-18.125-8.5-10.75-19T256 304t3.125-20.5 10.75-19T288 256t18.125 8.5 10.75 19T320 304zm40 0q0-30-17.25-51T296 232q-10.25 0-48.75 5.25Q229.5 240 208 240t-39.25-2.75Q130.75 232 120 232q-29.5 0-46.75 21T56 304q0 22 8 38.375t20.25 25.75 30.5 15 35 7.375 37.25 1.75h42q20.5 0 37.25-1.75t35-7.375 30.5-15 20.25-25.75T360 304zm56-44q0 51.75-15.25 82.75-9.5 19.25-26.375 33.25t-35.25 21.5-42.5 11.875-42.875 5.5T212 416q-19.5 0-35.5-.75t-36.875-3.125-38.125-7.5-34.25-12.875T37 371.5t-21.5-28.75Q0 312 0 260q0-59.25 34-99-6.75-20.5-6.75-42.5 0-29 12.75-54.5 27 0 47.5 9.875t47.25 30.875Q171.5 96 212 96q37 0 70 8 26.25-20.5 46.75-30.25T376 64q12.75 25.5 12.75 54.5 0 21.75-6.75 42 34 40 34 99.5z"/></svg>
        
      </defs>
    </svg>
    <input class="md-toggle" data-md-toggle="drawer" type="checkbox" id="__drawer" autocomplete="off">
    <input class="md-toggle" data-md-toggle="search" type="checkbox" id="__search" autocomplete="off">
    <label class="md-overlay" data-md-component="overlay" for="__drawer"></label>
    
    
      <header class="md-header" data-md-component="header">
  <nav class="md-header-nav md-grid">
    <div class="md-flex">
      <div class="md-flex__cell md-flex__cell--shrink">
        <a href="https://hrbust-acm.online" title="Hrbust_ACM's Wiki" aria-label="Hrbust_ACM's Wiki" class="md-header-nav__button md-logo">
          
            <i class="md-icon"></i>
          
        </a>
      </div>
      <div class="md-flex__cell md-flex__cell--shrink">
        <label class="md-icon md-icon--menu md-header-nav__button" for="__drawer"></label>
      </div>
      <div class="md-flex__cell md-flex__cell--stretch">
        <div class="md-flex__ellipsis md-header-nav__title" data-md-component="title">
          
            <span class="md-header-nav__topic">
              Hrbust_ACM's Wiki
            </span>
            <span class="md-header-nav__topic">
              
                凸包的求取
              
            </span>
          
        </div>
      </div>
      <div class="md-flex__cell md-flex__cell--shrink">
        
          <label class="md-icon md-icon--search md-header-nav__button" for="__search"></label>
          
<div class="md-search" data-md-component="search" role="dialog">
  <label class="md-search__overlay" for="__search"></label>
  <div class="md-search__inner" role="search">
    <form class="md-search__form" name="search">
      <input type="text" class="md-search__input" aria-label="search" name="query" placeholder="搜索" autocapitalize="off" autocorrect="off" autocomplete="off" spellcheck="false" data-md-component="query" data-md-state="active">
      <label class="md-icon md-search__icon" for="__search"></label>
      <button type="reset" class="md-icon md-search__icon" data-md-component="reset" tabindex="-1">
        &#xE5CD;
      </button>
    </form>
    <div class="md-search__output">
      <div class="md-search__scrollwrap" data-md-scrollfix>
        <div class="md-search-result" data-md-component="result">
          <div class="md-search-result__meta">
            键入以开始搜索
          </div>
          <ol class="md-search-result__list"></ol>
        </div>
      </div>
    </div>
  </div>
</div>
        
      </div>
      
        <div class="md-flex__cell md-flex__cell--shrink">
          <div class="md-header-nav__source">
            


  

<a href="https://github.com/acm-hrbust-wiki/wiki/tree/" title="前往 Github 仓库" class="md-source" data-md-source="github">
  
    <div class="md-source__icon">
      <svg viewBox="0 0 24 24" width="24" height="24">
        <use xlink:href="#__github" width="24" height="24"></use>
      </svg>
    </div>
  
  <div class="md-source__repository">
    acm-hrbust-wiki/wiki
  </div>
</a>
          </div>
        </div>
      
    </div>
  </nav>
</header>
    
    <div class="md-container">
      
        
      
      
        

  

<nav class="md-tabs md-tabs--active" data-md-component="tabs">
  <div class="md-tabs__inner md-grid">
    <ul class="md-tabs__list">
      
        
  
  
    <li class="md-tabs__item">
      
        <a href="../.." class="md-tabs__link">
          首页
        </a>
      
    </li>
  

      
        
  
  
    <li class="md-tabs__item">
      
        <a href="../../S/DFS/" class="md-tabs__link">
          搜索
        </a>
      
    </li>
  

      
        
  
  
    <li class="md-tabs__item">
      
        <a href="../../DP/%E7%8A%B6%E5%8E%8BDP/" class="md-tabs__link">
          动态规划
        </a>
      
    </li>
  

      
        
  
  
    <li class="md-tabs__item">
      
        <a href="../../Data_Structure/%E6%A0%91%E7%8A%B6%E6%95%B0%E7%BB%841/" class="md-tabs__link">
          数据结构
        </a>
      
    </li>
  

      
        
  
  
    
    
  
  
    <li class="md-tabs__item">
      
        <a href="../../Graph/%E5%8C%88%E7%89%99%E5%88%A9%E7%AE%97%E6%B3%95/" class="md-tabs__link">
          图论
        </a>
      
    </li>
  

  

      
        
  
  
    <li class="md-tabs__item">
      
        <a href="../../String/%E5%AD%97%E5%85%B8%E6%A0%91/" class="md-tabs__link">
          字符串
        </a>
      
    </li>
  

      
        
  
  
    <li class="md-tabs__item">
      
        <a href="../%E7%82%B9%E7%A7%AF%E5%8F%89%E7%A7%AF%E7%9A%84%E8%BF%90%E7%94%A8/" class="md-tabs__link md-tabs__link--active">
          计算几何
        </a>
      
    </li>
  

      
        
  
  
    <li class="md-tabs__item">
      
        <a href="../../Others/Time/" class="md-tabs__link">
          附录
        </a>
      
    </li>
  

      
    </ul>
  </div>
</nav>
      
      <main class="md-main" role="main">
        <div class="md-main__inner md-grid" data-md-component="container">
          
            
              <div class="md-sidebar md-sidebar--primary" data-md-component="navigation">
                <div class="md-sidebar__scrollwrap">
                  <div class="md-sidebar__inner">
                    <nav class="md-nav md-nav--primary" data-md-level="0">
  <label class="md-nav__title md-nav__title--site" for="__drawer">
    <a href="https://hrbust-acm.online" title="Hrbust_ACM's Wiki" class="md-nav__button md-logo">
      
        <i class="md-icon"></i>
      
    </a>
    Hrbust_ACM's Wiki
  </label>
  
    <div class="md-nav__source">
      


  

<a href="https://github.com/acm-hrbust-wiki/wiki/tree/" title="前往 Github 仓库" class="md-source" data-md-source="github">
  
    <div class="md-source__icon">
      <svg viewBox="0 0 24 24" width="24" height="24">
        <use xlink:href="#__github" width="24" height="24"></use>
      </svg>
    </div>
  
  <div class="md-source__repository">
    acm-hrbust-wiki/wiki
  </div>
</a>
    </div>
  
  <ul class="md-nav__list" data-md-scrollfix>
    
      
      
      


  <li class="md-nav__item md-nav__item--nested">
    
      <input class="md-toggle md-nav__toggle" data-md-toggle="nav-1" type="checkbox" id="nav-1">
    
    <label class="md-nav__link" for="nav-1">
      首页
    </label>
    <nav class="md-nav" data-md-component="collapsible" data-md-level="1">
      <label class="md-nav__title" for="nav-1">
        首页
      </label>
      <ul class="md-nav__list" data-md-scrollfix>
        
        
          
          
          


  <li class="md-nav__item">
    <a href="../.." title="Getting Started" class="md-nav__link">
      Getting Started
    </a>
  </li>

        
          
          
          


  <li class="md-nav__item">
    <a href="../../home/" title="Wiki介绍" class="md-nav__link">
      Wiki介绍
    </a>
  </li>

        
          
          
          


  <li class="md-nav__item">
    <a href="../../faq/" title="如何使用" class="md-nav__link">
      如何使用
    </a>
  </li>

        
      </ul>
    </nav>
  </li>

    
      
      
      


  <li class="md-nav__item md-nav__item--nested">
    
      <input class="md-toggle md-nav__toggle" data-md-toggle="nav-2" type="checkbox" id="nav-2">
    
    <label class="md-nav__link" for="nav-2">
      搜索
    </label>
    <nav class="md-nav" data-md-component="collapsible" data-md-level="1">
      <label class="md-nav__title" for="nav-2">
        搜索
      </label>
      <ul class="md-nav__list" data-md-scrollfix>
        
        
          
          
          


  <li class="md-nav__item">
    <a href="../../S/DFS/" title="深度优先搜索" class="md-nav__link">
      深度优先搜索
    </a>
  </li>

        
          
          
          


  <li class="md-nav__item">
    <a href="../../S/BFS/" title="广度优先搜索" class="md-nav__link">
      广度优先搜索
    </a>
  </li>

        
          
          
          


  <li class="md-nav__item">
    <a href="../../S/DeSearch/" title="双向搜索" class="md-nav__link">
      双向搜索
    </a>
  </li>

        
          
          
          


  <li class="md-nav__item">
    <a href="../../S/Memory_Search/" title="记忆化搜索" class="md-nav__link">
      记忆化搜索
    </a>
  </li>

        
          
          
          


  <li class="md-nav__item">
    <a href="../../S/%E6%9E%81%E5%A4%A7%E6%9E%81%E5%B0%8F%E6%90%9C%E7%B4%A2-alpha-beta%E5%89%AA%E6%9E%9D/" title="极大极小化搜索" class="md-nav__link">
      极大极小化搜索
    </a>
  </li>

        
          
          
          


  <li class="md-nav__item">
    <a href="../../S/%E5%90%AF%E5%8F%91%E5%BC%8F%E6%90%9C%E7%B4%A2/" title="启发式搜索" class="md-nav__link">
      启发式搜索
    </a>
  </li>

        
      </ul>
    </nav>
  </li>

    
      
      
      


  <li class="md-nav__item md-nav__item--nested">
    
      <input class="md-toggle md-nav__toggle" data-md-toggle="nav-3" type="checkbox" id="nav-3">
    
    <label class="md-nav__link" for="nav-3">
      动态规划
    </label>
    <nav class="md-nav" data-md-component="collapsible" data-md-level="1">
      <label class="md-nav__title" for="nav-3">
        动态规划
      </label>
      <ul class="md-nav__list" data-md-scrollfix>
        
        
          
          
          


  <li class="md-nav__item">
    <a href="../../DP/%E7%8A%B6%E5%8E%8BDP/" title="状态压缩DP" class="md-nav__link">
      状态压缩DP
    </a>
  </li>

        
          
          
          


  <li class="md-nav__item">
    <a href="../../DP/%E6%A0%91%E5%BD%A2DP/" title="树形 DP" class="md-nav__link">
      树形 DP
    </a>
  </li>

        
          
          
          


  <li class="md-nav__item">
    <a href="../../DP/%E5%8C%BA%E9%97%B4DP/" title="区间 DP" class="md-nav__link">
      区间 DP
    </a>
  </li>

        
          
          
          


  <li class="md-nav__item">
    <a href="../../DP/%E6%95%B0%E4%BD%8DDP/" title="数位 DP" class="md-nav__link">
      数位 DP
    </a>
  </li>

        
          
          
          


  <li class="md-nav__item">
    <a href="../../DP/%E6%A6%82%E7%8E%87DP/" title="概率 DP" class="md-nav__link">
      概率 DP
    </a>
  </li>

        
          
          
          


  <li class="md-nav__item">
    <a href="../../DP/%E6%9C%9F%E6%9C%9BDP/" title="期望 DP" class="md-nav__link">
      期望 DP
    </a>
  </li>

        
      </ul>
    </nav>
  </li>

    
      
      
      


  <li class="md-nav__item md-nav__item--nested">
    
      <input class="md-toggle md-nav__toggle" data-md-toggle="nav-4" type="checkbox" id="nav-4">
    
    <label class="md-nav__link" for="nav-4">
      数据结构
    </label>
    <nav class="md-nav" data-md-component="collapsible" data-md-level="1">
      <label class="md-nav__title" for="nav-4">
        数据结构
      </label>
      <ul class="md-nav__list" data-md-scrollfix>
        
        
          
          
          


  <li class="md-nav__item">
    <a href="../../Data_Structure/%E6%A0%91%E7%8A%B6%E6%95%B0%E7%BB%841/" title="一维树状数组" class="md-nav__link">
      一维树状数组
    </a>
  </li>

        
          
          
          


  <li class="md-nav__item">
    <a href="../../Data_Structure/%E6%A0%91%E7%8A%B6%E6%95%B0%E7%BB%842/" title="二维树状数组" class="md-nav__link">
      二维树状数组
    </a>
  </li>

        
          
          
          


  <li class="md-nav__item">
    <a href="../../Data_Structure/ST/" title="ST表" class="md-nav__link">
      ST表
    </a>
  </li>

        
          
          
          


  <li class="md-nav__item">
    <a href="../../Data_Structure/RMQ/" title="RMQ" class="md-nav__link">
      RMQ
    </a>
  </li>

        
          
          
          


  <li class="md-nav__item md-nav__item--nested">
    
      <input class="md-toggle md-nav__toggle" data-md-toggle="nav-4-5" type="checkbox" id="nav-4-5">
    
    <label class="md-nav__link" for="nav-4-5">
      线段树
    </label>
    <nav class="md-nav" data-md-component="collapsible" data-md-level="2">
      <label class="md-nav__title" for="nav-4-5">
        线段树
      </label>
      <ul class="md-nav__list" data-md-scrollfix>
        
        
          
          
          


  <li class="md-nav__item">
    <a href="../../Data_Structure/%E7%BA%BF%E6%AE%B5%E6%A0%91lazy/" title="线段树lazy标记" class="md-nav__link">
      线段树lazy标记
    </a>
  </li>

        
          
          
          


  <li class="md-nav__item">
    <a href="../../Data_Structure/%E7%BA%BF%E6%AE%B5%E6%A0%91%E5%8C%BA%E9%97%B4%E5%90%88%E5%B9%B6/" title="线段树区间合并" class="md-nav__link">
      线段树区间合并
    </a>
  </li>

        
          
          
          


  <li class="md-nav__item">
    <a href="../../Data_Structure/%E6%89%AB%E6%8F%8F%E7%BA%BF/" title="扫描线" class="md-nav__link">
      扫描线
    </a>
  </li>

        
      </ul>
    </nav>
  </li>

        
          
          
          


  <li class="md-nav__item md-nav__item--nested">
    
      <input class="md-toggle md-nav__toggle" data-md-toggle="nav-4-6" type="checkbox" id="nav-4-6">
    
    <label class="md-nav__link" for="nav-4-6">
      树链剖分
    </label>
    <nav class="md-nav" data-md-component="collapsible" data-md-level="2">
      <label class="md-nav__title" for="nav-4-6">
        树链剖分
      </label>
      <ul class="md-nav__list" data-md-scrollfix>
        
        
          
          
          


  <li class="md-nav__item">
    <a href="../../Data_Structure/%E7%82%B9%E5%88%A8/" title="点剖" class="md-nav__link">
      点剖
    </a>
  </li>

        
          
          
          


  <li class="md-nav__item">
    <a href="../../Data_Structure/%E8%BE%B9%E5%89%96/" title="边剖" class="md-nav__link">
      边剖
    </a>
  </li>

        
      </ul>
    </nav>
  </li>

        
          
          
          


  <li class="md-nav__item">
    <a href="../../Data_Structure/%E5%88%86%E5%9D%97/" title="分块算法" class="md-nav__link">
      分块算法
    </a>
  </li>

        
          
          
          


  <li class="md-nav__item">
    <a href="../../Data_Structure/%E8%8E%AB%E9%98%9F/" title="莫队算法" class="md-nav__link">
      莫队算法
    </a>
  </li>

        
          
          
          


  <li class="md-nav__item">
    <a href="../../Data_Structure/%E7%82%B9%E5%88%86%E6%B2%BB/" title="点分治" class="md-nav__link">
      点分治
    </a>
  </li>

        
      </ul>
    </nav>
  </li>

    
      
      
      


  <li class="md-nav__item md-nav__item--nested">
    
      <input class="md-toggle md-nav__toggle" data-md-toggle="nav-5" type="checkbox" id="nav-5">
    
    <label class="md-nav__link" for="nav-5">
      图论
    </label>
    <nav class="md-nav" data-md-component="collapsible" data-md-level="1">
      <label class="md-nav__title" for="nav-5">
        图论
      </label>
      <ul class="md-nav__list" data-md-scrollfix>
        
        
          
          
          


  <li class="md-nav__item md-nav__item--nested">
    
      <input class="md-toggle md-nav__toggle" data-md-toggle="nav-5-1" type="checkbox" id="nav-5-1">
    
    <label class="md-nav__link" for="nav-5-1">
      二分图
    </label>
    <nav class="md-nav" data-md-component="collapsible" data-md-level="2">
      <label class="md-nav__title" for="nav-5-1">
        二分图
      </label>
      <ul class="md-nav__list" data-md-scrollfix>
        
        
          
          
          


  <li class="md-nav__item">
    <a href="../../Graph/%E5%8C%88%E7%89%99%E5%88%A9%E7%AE%97%E6%B3%95/" title="匈牙利算法" class="md-nav__link">
      匈牙利算法
    </a>
  </li>

        
          
          
          


  <li class="md-nav__item">
    <a href="../../Graph/KM%E7%AE%97%E6%B3%95/" title="KM 算法" class="md-nav__link">
      KM 算法
    </a>
  </li>

        
      </ul>
    </nav>
  </li>

        
          
          
          


  <li class="md-nav__item md-nav__item--nested">
    
      <input class="md-toggle md-nav__toggle" data-md-toggle="nav-5-2" type="checkbox" id="nav-5-2">
    
    <label class="md-nav__link" for="nav-5-2">
      网络流
    </label>
    <nav class="md-nav" data-md-component="collapsible" data-md-level="2">
      <label class="md-nav__title" for="nav-5-2">
        网络流
      </label>
      <ul class="md-nav__list" data-md-scrollfix>
        
        
          
          
          


  <li class="md-nav__item">
    <a href="../../Graph/EK/" title="EK 算法" class="md-nav__link">
      EK 算法
    </a>
  </li>

        
          
          
          


  <li class="md-nav__item">
    <a href="../../Graph/Dinic/" title="Dinic+当前弧优化" class="md-nav__link">
      Dinic+当前弧优化
    </a>
  </li>

        
          
          
          


  <li class="md-nav__item">
    <a href="../../Graph/ISAP/" title="ISAP算法" class="md-nav__link">
      ISAP算法
    </a>
  </li>

        
      </ul>
    </nav>
  </li>

        
          
          
          


  <li class="md-nav__item md-nav__item--nested">
    
      <input class="md-toggle md-nav__toggle" data-md-toggle="nav-5-3" type="checkbox" id="nav-5-3">
    
    <label class="md-nav__link" for="nav-5-3">
      费用流
    </label>
    <nav class="md-nav" data-md-component="collapsible" data-md-level="2">
      <label class="md-nav__title" for="nav-5-3">
        费用流
      </label>
      <ul class="md-nav__list" data-md-scrollfix>
        
        
          
          
          


  <li class="md-nav__item">
    <a href="../../Graph/SPFA%E8%B4%B9%E7%94%A8%E6%B5%81/" title="SPFA 费用流" class="md-nav__link">
      SPFA 费用流
    </a>
  </li>

        
      </ul>
    </nav>
  </li>

        
      </ul>
    </nav>
  </li>

    
      
      
      


  <li class="md-nav__item md-nav__item--nested">
    
      <input class="md-toggle md-nav__toggle" data-md-toggle="nav-6" type="checkbox" id="nav-6">
    
    <label class="md-nav__link" for="nav-6">
      字符串
    </label>
    <nav class="md-nav" data-md-component="collapsible" data-md-level="1">
      <label class="md-nav__title" for="nav-6">
        字符串
      </label>
      <ul class="md-nav__list" data-md-scrollfix>
        
        
          
          
          


  <li class="md-nav__item">
    <a href="../../String/%E5%AD%97%E5%85%B8%E6%A0%91/" title="字典树" class="md-nav__link">
      字典树
    </a>
  </li>

        
          
          
          


  <li class="md-nav__item">
    <a href="../../String/AC%E8%87%AA%E5%8A%A8%E6%9C%BA/" title="AC自动机" class="md-nav__link">
      AC自动机
    </a>
  </li>

        
      </ul>
    </nav>
  </li>

    
      
      
      

  


  <li class="md-nav__item md-nav__item--active md-nav__item--nested">
    
      <input class="md-toggle md-nav__toggle" data-md-toggle="nav-7" type="checkbox" id="nav-7" checked>
    
    <label class="md-nav__link" for="nav-7">
      计算几何
    </label>
    <nav class="md-nav" data-md-component="collapsible" data-md-level="1">
      <label class="md-nav__title" for="nav-7">
        计算几何
      </label>
      <ul class="md-nav__list" data-md-scrollfix>
        
        
          
          
          


  <li class="md-nav__item">
    <a href="../%E7%82%B9%E7%A7%AF%E5%8F%89%E7%A7%AF%E7%9A%84%E8%BF%90%E7%94%A8/" title="点积叉积的运用" class="md-nav__link">
      点积叉积的运用
    </a>
  </li>

        
          
          
          

  


  <li class="md-nav__item md-nav__item--active">
    
    <input class="md-toggle md-nav__toggle" data-md-toggle="toc" type="checkbox" id="__toc">
    
    
    <a href="./" title="凸包的求取" class="md-nav__link md-nav__link--active">
      凸包的求取
    </a>
    
  </li>

        
          
          
          


  <li class="md-nav__item">
    <a href="../%E5%8D%8A%E5%B9%B3%E9%9D%A2%E4%BA%A4/" title="半平面交" class="md-nav__link">
      半平面交
    </a>
  </li>

        
          
          
          


  <li class="md-nav__item">
    <a href="../%E6%97%8B%E8%BD%AC%E5%8D%A1%E5%A3%B3/" title="旋转卡壳" class="md-nav__link">
      旋转卡壳
    </a>
  </li>

        
      </ul>
    </nav>
  </li>

    
      
      
      


  <li class="md-nav__item md-nav__item--nested">
    
      <input class="md-toggle md-nav__toggle" data-md-toggle="nav-8" type="checkbox" id="nav-8">
    
    <label class="md-nav__link" for="nav-8">
      附录
    </label>
    <nav class="md-nav" data-md-component="collapsible" data-md-level="1">
      <label class="md-nav__title" for="nav-8">
        附录
      </label>
      <ul class="md-nav__list" data-md-scrollfix>
        
        
          
          
          


  <li class="md-nav__item">
    <a href="../../Others/Time/" title="时间/空间复杂度" class="md-nav__link">
      时间/空间复杂度
    </a>
  </li>

        
          
          
          


  <li class="md-nav__item">
    <a href="../../Others/exem/" title="习题" class="md-nav__link">
      习题
    </a>
  </li>

        
      </ul>
    </nav>
  </li>

    
  </ul>
</nav>
                  </div>
                </div>
              </div>
            
            
          
          <div class="md-content">
            <article class="md-content__inner md-typeset">
              
                
                  <a href="https://github.com/acm-hrbust-wiki/wiki/tree/docs/Geometry/凸包的求取.md" title="编辑此页" class="md-icon md-content__icon">&#xE3C9;</a>
                
                
                  <h1>凸包的求取</h1>
                
                <p>poj 1912; 题意：给定平面上 n 个点，之后给定若干直线，询问所有点时候在直线的一侧；</p>
<p><strong>思路：</strong>首先求取凸包，之后将凸包上的每一条边的倾斜角求出，对倾斜角二分，找出倾斜 角最接近给定直线倾斜角的边所对应的点，将直线旋转 180°后在求出对应点，判定所求两 点是否在直线两侧</p>
<table class="codehilitetable"><tr><td class="linenos"><div class="linenodiv"><pre><span></span> 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91</pre></div></td><td class="code"><div class="codehilite"><pre><span></span><code><span class="k">struct</span> <span class="n">Line</span>
<span class="p">{</span>
    <span class="n">Point</span> <span class="n">p</span><span class="p">;</span>
    <span class="n">Vector</span> <span class="n">v</span><span class="p">;</span>
    <span class="kt">double</span> <span class="n">ang</span><span class="p">;</span>
    <span class="n">Line</span><span class="p">()</span> <span class="p">{}</span>
    <span class="n">Line</span><span class="p">(</span><span class="n">Point</span> <span class="n">p</span><span class="p">,</span> <span class="n">Vector</span> <span class="n">v</span><span class="p">)</span> <span class="o">:</span> <span class="n">p</span><span class="p">(</span><span class="n">p</span><span class="p">),</span> <span class="n">v</span><span class="p">(</span><span class="n">v</span><span class="p">)</span> <span class="p">{</span> <span class="n">ang</span> <span class="o">=</span> <span class="n">atan2</span><span class="p">(</span><span class="n">v</span><span class="p">.</span><span class="n">y</span><span class="p">,</span> <span class="n">v</span><span class="p">.</span><span class="n">x</span><span class="p">);</span> <span class="p">}</span>
    <span class="n">Point</span> <span class="n">point</span><span class="p">(</span><span class="kt">double</span> <span class="n">t</span><span class="p">)</span> <span class="p">{</span> <span class="k">return</span> <span class="n">p</span> <span class="o">+</span> <span class="n">v</span> <span class="o">*</span> <span class="n">t</span><span class="p">;</span> <span class="p">}</span>       <span class="c1">//求取直线上的某一个点</span>
    <span class="kt">bool</span> <span class="k">operator</span><span class="o">&lt;</span><span class="p">(</span><span class="n">Line</span> <span class="o">&amp;</span><span class="n">l</span><span class="p">)</span> <span class="p">{</span> <span class="k">return</span> <span class="n">ang</span> <span class="o">&lt;</span> <span class="n">l</span><span class="p">.</span><span class="n">ang</span><span class="p">;</span> <span class="p">}</span>   <span class="c1">//直线默认以倾斜角排序</span>
    <span class="kt">int</span> <span class="n">Onleft</span><span class="p">(</span><span class="n">Point</span> <span class="n">P</span><span class="p">)</span> <span class="p">{</span> <span class="k">return</span> <span class="n">dcmp</span><span class="p">(</span><span class="n">v</span> <span class="o">^</span> <span class="p">(</span><span class="n">P</span> <span class="o">-</span> <span class="n">p</span><span class="p">));</span> <span class="p">}</span> <span class="c1">//判断一个点是否在直线的左</span>
    <span class="err">侧</span>
        <span class="n">Point</span>
        <span class="k">operator</span><span class="o">&amp;</span><span class="p">(</span><span class="n">Line</span> <span class="o">&amp;</span><span class="n">l</span><span class="p">)</span> <span class="c1">//求取两直线的交点</span>
    <span class="p">{</span>
        <span class="n">Vector</span> <span class="n">u</span> <span class="o">=</span> <span class="n">p</span> <span class="o">-</span> <span class="n">l</span><span class="p">.</span><span class="n">p</span><span class="p">;</span>
        <span class="kt">double</span> <span class="n">t</span> <span class="o">=</span> <span class="p">(</span><span class="n">l</span><span class="p">.</span><span class="n">v</span> <span class="o">^</span> <span class="n">u</span><span class="p">)</span> <span class="o">/</span> <span class="p">(</span><span class="n">v</span> <span class="o">^</span> <span class="n">l</span><span class="p">.</span><span class="n">v</span><span class="p">);</span>
        <span class="k">return</span> <span class="n">p</span> <span class="o">+</span> <span class="n">v</span> <span class="o">*</span> <span class="n">t</span><span class="p">;</span>
    <span class="p">}</span>
<span class="p">};</span>
<span class="n">Point</span> <span class="n">p</span><span class="p">[</span><span class="n">N</span><span class="p">],</span> <span class="n">sta</span><span class="p">[</span><span class="n">N</span><span class="p">];</span>
<span class="kt">int</span> <span class="n">n</span><span class="p">,</span> <span class="n">top</span><span class="p">;</span>
<span class="kt">double</span> <span class="n">af</span><span class="p">[</span><span class="n">N</span><span class="p">];</span> <span class="c1">//用于记录凸包每一条边的倾斜角</span>
<span class="n">Line</span> <span class="n">l</span><span class="p">;</span>
<span class="kt">bool</span> <span class="nf">cmp</span><span class="p">(</span><span class="n">Point</span> <span class="n">a</span><span class="p">,</span> <span class="n">Point</span> <span class="n">b</span><span class="p">)</span> <span class="c1">//极角排序</span>
<span class="p">{</span>
    <span class="n">Vector</span> <span class="n">v</span> <span class="o">=</span> <span class="n">a</span> <span class="o">-</span> <span class="n">p</span><span class="p">[</span><span class="mi">0</span><span class="p">],</span> <span class="n">w</span> <span class="o">=</span> <span class="n">b</span> <span class="o">-</span> <span class="n">p</span><span class="p">[</span><span class="mi">0</span><span class="p">];</span> <span class="c1">//以某一点为基准求出其他所有点相对于它的极角</span>
    <span class="mi">83</span> <span class="k">if</span> <span class="p">(</span><span class="n">dcmp</span><span class="p">(</span><span class="n">v</span> <span class="o">^</span> <span class="n">w</span><span class="p">)</span> <span class="o">&lt;</span> <span class="mi">0</span><span class="p">)</span> <span class="k">return</span> <span class="nb">false</span><span class="p">;</span>
    <span class="k">else</span> <span class="k">if</span> <span class="p">(</span><span class="o">!</span><span class="n">dcmp</span><span class="p">(</span><span class="n">v</span> <span class="o">^</span> <span class="n">w</span><span class="p">)</span> <span class="o">&amp;&amp;</span> <span class="n">dcmp</span><span class="p">(</span><span class="n">sqr</span><span class="p">(</span><span class="n">v</span><span class="p">)</span> <span class="o">-</span> <span class="n">sqr</span><span class="p">(</span><span class="n">w</span><span class="p">))</span> <span class="o">&gt;</span> <span class="mi">0</span><span class="p">)</span> <span class="k">return</span> <span class="nb">false</span><span class="p">;</span> <span class="c1">//极角相同以向量模长</span>
    <span class="err">排序</span>
    <span class="k">return</span> <span class="nb">true</span><span class="p">;</span>
<span class="p">}</span>
<span class="kt">void</span> <span class="nf">graham</span><span class="p">()</span> <span class="c1">//凸包</span>
<span class="p">{</span>
    <span class="n">sort</span><span class="p">(</span><span class="n">p</span> <span class="o">+</span> <span class="mi">1</span><span class="p">,</span> <span class="n">p</span> <span class="o">+</span> <span class="n">n</span><span class="p">,</span> <span class="n">cmp</span><span class="p">);</span>
    <span class="n">n</span> <span class="o">=</span> <span class="n">unique</span><span class="p">(</span><span class="n">p</span><span class="p">,</span> <span class="n">p</span> <span class="o">+</span> <span class="n">n</span><span class="p">)</span> <span class="o">-</span> <span class="n">p</span><span class="p">;</span>
    <span class="kt">int</span> <span class="n">t</span> <span class="o">=</span> <span class="n">n</span> <span class="o">-</span> <span class="mi">1</span><span class="p">;</span>
    <span class="k">while</span> <span class="p">(</span><span class="n">t</span> <span class="o">&amp;&amp;</span> <span class="o">!</span><span class="p">((</span><span class="n">p</span><span class="p">[</span><span class="n">n</span> <span class="o">-</span> <span class="mi">1</span><span class="p">]</span> <span class="o">-</span> <span class="n">p</span><span class="p">[</span><span class="mi">0</span><span class="p">])</span> <span class="o">^</span> <span class="p">(</span><span class="n">p</span><span class="p">[</span><span class="n">t</span><span class="p">]</span> <span class="o">-</span> <span class="n">p</span><span class="p">[</span><span class="mi">0</span><span class="p">])))</span>
        <span class="n">t</span><span class="o">--</span><span class="p">;</span>
    <span class="k">if</span> <span class="p">(</span><span class="o">!</span><span class="n">t</span><span class="p">)</span> <span class="c1">//当凸包退化为一个点或者一条直线时的情况</span>
    <span class="p">{</span>
        <span class="n">sta</span><span class="p">[</span><span class="mi">0</span><span class="p">]</span> <span class="o">=</span> <span class="n">p</span><span class="p">[</span><span class="mi">0</span><span class="p">];</span>
        <span class="n">top</span> <span class="o">=</span> <span class="mi">1</span><span class="p">;</span>
        <span class="k">if</span> <span class="p">(</span><span class="n">n</span> <span class="o">&gt;</span> <span class="mi">1</span><span class="p">)</span>
            <span class="n">sta</span><span class="p">[</span><span class="mi">1</span><span class="p">]</span> <span class="o">=</span> <span class="n">p</span><span class="p">[</span><span class="n">n</span> <span class="o">-</span> <span class="mi">1</span><span class="p">],</span> <span class="n">top</span> <span class="o">=</span> <span class="mi">2</span><span class="p">;</span>
        <span class="k">return</span><span class="p">;</span>
    <span class="p">}</span>
    <span class="n">reverse</span><span class="p">(</span><span class="n">p</span> <span class="o">+</span> <span class="n">t</span> <span class="o">+</span> <span class="mi">1</span><span class="p">,</span> <span class="n">p</span> <span class="o">+</span> <span class="n">n</span><span class="p">);</span> <span class="c1">//为求取所有在凸包边界上的点</span>
    <span class="n">sta</span><span class="p">[</span><span class="n">top</span><span class="o">++</span><span class="p">]</span> <span class="o">=</span> <span class="n">p</span><span class="p">[</span><span class="mi">0</span><span class="p">];</span>
    <span class="n">sta</span><span class="p">[</span><span class="n">top</span><span class="o">++</span><span class="p">]</span> <span class="o">=</span> <span class="n">p</span><span class="p">[</span><span class="mi">1</span><span class="p">];</span>
    <span class="n">p</span><span class="p">[</span><span class="n">n</span><span class="o">++</span><span class="p">]</span> <span class="o">=</span> <span class="n">p</span><span class="p">[</span><span class="mi">0</span><span class="p">];</span>
    <span class="k">for</span> <span class="p">(</span><span class="kt">int</span> <span class="n">i</span> <span class="o">=</span> <span class="mi">2</span><span class="p">;</span> <span class="n">i</span> <span class="o">&lt;</span> <span class="n">n</span><span class="p">;</span> <span class="n">i</span><span class="o">++</span><span class="p">)</span>
    <span class="p">{</span>
        <span class="k">while</span> <span class="p">(</span><span class="n">top</span> <span class="o">&gt;</span> <span class="mi">1</span> <span class="o">&amp;&amp;</span> <span class="p">((</span><span class="n">sta</span><span class="p">[</span><span class="n">top</span> <span class="o">-</span> <span class="mi">1</span><span class="p">]</span> <span class="o">-</span> <span class="n">sta</span><span class="p">[</span><span class="n">top</span> <span class="o">-</span> <span class="mi">2</span><span class="p">])</span> <span class="o">^</span> <span class="p">(</span><span class="n">p</span><span class="p">[</span><span class="n">i</span><span class="p">]</span> <span class="o">-</span> <span class="n">sta</span><span class="p">[</span><span class="n">top</span> <span class="o">-</span> <span class="mi">2</span><span class="p">]))</span> <span class="o">&lt;=</span> <span class="mi">0</span><span class="p">)</span>
            <span class="n">top</span><span class="o">--</span><span class="p">;</span>
        <span class="err">确定每</span>
        <span class="err">一个角都不为优角</span>
        <span class="n">sta</span><span class="p">[</span><span class="n">top</span><span class="o">++</span><span class="p">]</span> <span class="o">=</span> <span class="n">p</span><span class="p">[</span><span class="n">i</span><span class="p">];</span>
    <span class="p">}</span>
    <span class="n">top</span><span class="o">--</span><span class="p">;</span>
    <span class="k">for</span> <span class="p">(</span><span class="kt">int</span> <span class="n">i</span> <span class="o">=</span> <span class="mi">0</span><span class="p">;</span> <span class="n">i</span> <span class="o">&lt;</span> <span class="n">top</span><span class="p">;</span> <span class="n">i</span><span class="o">++</span><span class="p">)</span>
        <span class="n">af</span><span class="p">[</span><span class="n">i</span><span class="p">]</span> <span class="o">=</span> <span class="n">atan2</span><span class="p">(</span><span class="n">sta</span><span class="p">[</span><span class="n">i</span> <span class="o">+</span> <span class="mi">1</span><span class="p">].</span><span class="n">y</span> <span class="o">-</span> <span class="n">sta</span><span class="p">[</span><span class="n">i</span><span class="p">].</span><span class="n">y</span><span class="p">,</span> <span class="n">sta</span><span class="p">[</span><span class="n">i</span> <span class="o">+</span> <span class="mi">1</span><span class="p">].</span><span class="n">x</span> <span class="o">-</span> <span class="n">sta</span><span class="p">[</span><span class="n">i</span><span class="p">].</span><span class="n">x</span><span class="p">);</span> <span class="c1">//求取所有边的倾斜角</span>
<span class="p">}</span>
<span class="kt">int</span> <span class="nf">main</span><span class="p">()</span>
<span class="p">{</span>
    <span class="n">scanf</span><span class="p">(</span><span class="s">&quot;%d&quot;</span><span class="p">,</span> <span class="o">&amp;</span><span class="n">n</span><span class="p">);</span>
    <span class="k">for</span> <span class="p">(</span><span class="kt">int</span> <span class="n">i</span> <span class="o">=</span> <span class="mi">0</span><span class="p">;</span> <span class="n">i</span> <span class="o">&lt;</span> <span class="n">n</span><span class="p">;</span> <span class="n">i</span><span class="o">++</span><span class="p">)</span>
    <span class="p">{</span>
        <span class="n">scanf</span><span class="p">(</span><span class="s">&quot;%lf %lf&quot;</span><span class="p">,</span> <span class="o">&amp;</span><span class="n">p</span><span class="p">[</span><span class="n">i</span><span class="p">].</span><span class="n">x</span><span class="p">,</span> <span class="o">&amp;</span><span class="n">p</span><span class="p">[</span><span class="n">i</span><span class="p">].</span><span class="n">y</span><span class="p">);</span>
        <span class="k">if</span> <span class="p">(</span><span class="n">p</span><span class="p">[</span><span class="n">i</span><span class="p">]</span> <span class="o">&lt;</span> <span class="n">p</span><span class="p">[</span><span class="mi">0</span><span class="p">])</span>
            <span class="n">swap</span><span class="p">(</span><span class="n">p</span><span class="p">[</span><span class="n">i</span><span class="p">],</span> <span class="n">p</span><span class="p">[</span><span class="mi">0</span><span class="p">]);</span>
    <span class="p">}</span>
    <span class="k">if</span> <span class="p">(</span><span class="n">n</span> <span class="o">&gt;</span> <span class="mi">1</span><span class="p">)</span>
        <span class="n">graham</span><span class="p">();</span>
    <span class="kt">double</span> <span class="n">a</span><span class="p">,</span> <span class="n">b</span><span class="p">,</span> <span class="n">c</span><span class="p">,</span> <span class="n">d</span><span class="p">;</span>
    <span class="k">while</span> <span class="p">(</span><span class="o">~</span><span class="n">scanf</span><span class="p">(</span><span class="s">&quot;%lf %lf %lf %lf&quot;</span><span class="p">,</span> <span class="o">&amp;</span><span class="n">a</span><span class="p">,</span> <span class="o">&amp;</span><span class="n">b</span><span class="p">,</span> <span class="o">&amp;</span><span class="n">c</span><span class="p">,</span> <span class="o">&amp;</span><span class="n">d</span><span class="p">))</span>
    <span class="p">{</span>
        <span class="k">if</span> <span class="p">(</span><span class="n">n</span> <span class="o">&lt;</span> <span class="mi">2</span><span class="p">)</span>
        <span class="p">{</span>
            <span class="n">puts</span><span class="p">(</span><span class="s">&quot;GOOD&quot;</span><span class="p">);</span>
            <span class="mi">84</span> <span class="k">continue</span><span class="p">;</span>
        <span class="p">}</span>
        <span class="n">l</span> <span class="o">=</span> <span class="n">Line</span><span class="p">(</span><span class="n">Point</span><span class="p">(</span><span class="n">a</span><span class="p">,</span> <span class="n">b</span><span class="p">),</span> <span class="n">Vector</span><span class="p">(</span><span class="n">c</span> <span class="o">-</span> <span class="n">a</span><span class="p">,</span> <span class="n">d</span> <span class="o">-</span> <span class="n">b</span><span class="p">));</span>
        <span class="kt">double</span> <span class="n">l1</span> <span class="o">=</span> <span class="n">atan2</span><span class="p">(</span><span class="n">l</span><span class="p">.</span><span class="n">v</span><span class="p">.</span><span class="n">y</span><span class="p">,</span> <span class="n">l</span><span class="p">.</span><span class="n">v</span><span class="p">.</span><span class="n">x</span><span class="p">),</span> <span class="n">l2</span> <span class="o">=</span> <span class="n">atan2</span><span class="p">(</span><span class="o">-</span><span class="n">l</span><span class="p">.</span><span class="n">v</span><span class="p">.</span><span class="n">y</span><span class="p">,</span> <span class="o">-</span><span class="n">l</span><span class="p">.</span><span class="n">v</span><span class="p">.</span><span class="n">x</span><span class="p">);</span>
        <span class="kt">int</span> <span class="n">p1</span> <span class="o">=</span> <span class="n">lower_bound</span><span class="p">(</span><span class="n">af</span><span class="p">,</span> <span class="n">af</span> <span class="o">+</span> <span class="n">top</span><span class="p">,</span> <span class="n">l1</span><span class="p">)</span> <span class="o">-</span> <span class="n">af</span><span class="p">;</span>
        <span class="kt">int</span> <span class="n">p2</span> <span class="o">=</span> <span class="n">lower_bound</span><span class="p">(</span><span class="n">af</span><span class="p">,</span> <span class="n">af</span> <span class="o">+</span> <span class="n">top</span><span class="p">,</span> <span class="n">l2</span><span class="p">)</span> <span class="o">-</span> <span class="n">af</span><span class="p">;</span>
        <span class="k">if</span> <span class="p">(</span><span class="n">l</span><span class="p">.</span><span class="n">Onleft</span><span class="p">(</span><span class="n">sta</span><span class="p">[</span><span class="n">p1</span><span class="p">])</span> <span class="o">*</span> <span class="n">l</span><span class="p">.</span><span class="n">Onleft</span><span class="p">(</span><span class="n">sta</span><span class="p">[</span><span class="n">p2</span><span class="p">])</span> <span class="o">&lt;</span> <span class="mi">0</span><span class="p">)</span>
            <span class="n">puts</span><span class="p">(</span><span class="s">&quot;BAD&quot;</span><span class="p">);</span>
        <span class="k">else</span>
            <span class="n">puts</span><span class="p">(</span><span class="s">&quot;GOOD&quot;</span><span class="p">);</span>
    <span class="p">}</span>
<span class="p">}</span>
</code></pre></div>
</td></tr></table>

<p>整理人：网络 18 – 3 冯紫君</p>
                
                  
                
                
              
              
                


              
            </article>
          </div>
        </div>
      </main>
      
        
<footer class="md-footer">
  
    <div class="md-footer-nav">
      <nav class="md-footer-nav__inner md-grid">
        
          <a href="../%E7%82%B9%E7%A7%AF%E5%8F%89%E7%A7%AF%E7%9A%84%E8%BF%90%E7%94%A8/" title="点积叉积的运用" class="md-flex md-footer-nav__link md-footer-nav__link--prev" rel="prev">
            <div class="md-flex__cell md-flex__cell--shrink">
              <i class="md-icon md-icon--arrow-back md-footer-nav__button"></i>
            </div>
            <div class="md-flex__cell md-flex__cell--stretch md-footer-nav__title">
              <span class="md-flex__ellipsis">
                <span class="md-footer-nav__direction">
                  上一页
                </span>
                点积叉积的运用
              </span>
            </div>
          </a>
        
        
          <a href="../%E5%8D%8A%E5%B9%B3%E9%9D%A2%E4%BA%A4/" title="半平面交" class="md-flex md-footer-nav__link md-footer-nav__link--next" rel="next">
            <div class="md-flex__cell md-flex__cell--stretch md-footer-nav__title">
              <span class="md-flex__ellipsis">
                <span class="md-footer-nav__direction">
                  下一页
                </span>
                半平面交
              </span>
            </div>
            <div class="md-flex__cell md-flex__cell--shrink">
              <i class="md-icon md-icon--arrow-forward md-footer-nav__button"></i>
            </div>
          </a>
        
      </nav>
    </div>
  
  <div class="md-footer-meta md-typeset">
    <div class="md-footer-meta__inner md-grid">
      <div class="md-footer-copyright">
        
        powered by
        <a href="https://www.mkdocs.org" target="_blank" rel="noopener">MkDocs</a>
        and
        <a href="https://squidfunk.github.io/mkdocs-material/" target="_blank" rel="noopener">
          Material for MkDocs</a>
      </div>
      
    </div>
  </div>
</footer>
      
    </div>
    
      <script src="../../assets/javascripts/application.c33a9706.js"></script>
      
        
        
          
          <script src="../../assets/javascripts/lunr/lunr.stemmer.support.js"></script>
          
            
              
                <script src="../../assets/javascripts/lunr/tinyseg.js"></script>
              
              
                <script src="../../assets/javascripts/lunr/lunr.ja.js"></script>
              
            
          
          
        
      
      <script>app.initialize({version:"1.1",url:{base:"../.."}})</script>
      
        <script src="https://cdnjs.loli.net/ajax/libs/mathjax/2.7.5/MathJax.js?config=TeX-MML-AM_CHTML"></script>
      
    
  </body>
</html>